#include"KMP.h"
#include<iostream>
KMP::KMP(string _target, string _match) :target(_target), findstr(_match)
{
	pattern_table = nullptr;
	loopcount = 0;
	printf("'%s' size %d\n", _target.c_str(), _target.size());
	printf("'%s' size %d\n", _match.c_str(), _match.size());
}

KMP::~KMP()
{
	if (pattern_table != nullptr)
	{
		delete[] pattern_table;
		pattern_table = nullptr;
	}
}

void KMP::StringInerMatchTable(const string& pattern)
{
	const int pattern_length = pattern.size();
	pattern_table = new int[pattern_length];
	//第一个元素，前面没有匹配项
	pattern_table[0] = 0;
	int matchCount = 0;
	int matchIndex = 0;
	for (int i = 1; i < pattern_length; i++)
	{
		loopcount++;//计算循环次数
		if (pattern[i] == pattern[matchIndex])
		{
			pattern_table[i] = ++matchCount;
			matchIndex++;
		}
		else
		{
			matchCount = 0;
			matchIndex = 0;
			pattern_table[i] = 0;
		}
		cout << pattern[i] << ":" << pattern_table[i] << endl;
	}
}

int KMP::FindMatch()
{
	StringInerMatchTable(findstr);
	if (target.size() < findstr.size())
		return -1;
	int targetLength = target.size();
	int patternIndex = 0;
	int i = 0;
	while (i < targetLength)
	{
		loopcount++;//计算循环次数
		if (target[i] != findstr[patternIndex])
		{	
			i++;
			continue;
		}
		else
		{//查找到相同部分，逐个匹配
			//cout << "target[" << i << "] " << target[i] << " == " << "findstr[" << patternIndex << "] " << findstr[patternIndex] << endl;
			int localIndex = i + 1;
			patternIndex++;
			while (target[localIndex] == findstr[patternIndex])
			{
				if (patternIndex == (findstr.size() - 1))
					return i;
				loopcount++;//计算循环次数
				localIndex++;
				patternIndex++;
			}

			//移动位数 = 已匹配的字符数 - 对应的部分匹配值
			int movepos = patternIndex - pattern_table[patternIndex - 1];
			//cout << "移动位数:" << movepos << endl;
			i =  movepos + i;
			patternIndex = 0;
			continue;
			
		}
		i++;
	}
	return -1;
}
